今天來解YKL30(UVA10193)：All You Need Is Love

All You Need Is Love

判斷2個二進制S1和S2是否存在某個二進制字串L
這兩個字串可以被L重複減去直到完全匹配
似於最大公因數 (GCD) 的概念
if(GCD不為1):
=>代表兩個字串可以被某個L組成
else:
=>不能被組成

#include <iostream>
#include <string>
using namespace std;

int gcd(int a,int b){
	if(a%b==0)return b;
	else return gcd(b,a%b);
}

int main(){
	int n,cases=1;
	cin >> n;
	while(cases <= n){
		string str1,str2;
		cin >> str1 >> str2;
		int S1=stoi(str1,nullptr,2);
		int S2=stoi(str2,nullptr,2);
	
		if(gcd(S1,S2) > 1){
			cout << "Pair #" << cases << ": All you need is love!" << endl;
		}else{
			cout << "Pair #" << cases << ": Love is not all you need!" << endl;
		}
		
		cases++;
	}
	return 0;
}